package 栈和队列;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/**
 * @description:
 * @author: ywk 全排列栈实现
 * @date: 2021-03-02
 */
public class PopRank {
    static int n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        // 元素个数
        Stack s = new Stack();
        Queue in = new LinkedList();
        Queue out = new LinkedList();
        for (int i = 1; i <= n; i++) {
            in.offer(i);
        }
        printAllOutStackSeq(in, s, out);
        sc.close();
    }

    public static void printAllOutStackSeq(Queue in, Stack stack, Queue out) {
        if (out.size() == n) {
            // 所有元素都出栈了
            while (!out.isEmpty()) {
                System.out.print(out.poll() + "");
            }
            System.out.println();
            return;
        }
        Queue inCopy = new LinkedList<>(in);
        Stack stackCopy = (Stack) stack.clone();
        Queue<Integer> outCopy = new LinkedList<>(out);
        if (!stack.empty()) {
            // 出栈，将元素出栈，push到结果队列中
            out.offer(stack.pop());
            printAllOutStackSeq(inCopy, stack, out);
        }
        if (!in.isEmpty()) {
            // 入栈，将输入队列出队，进行入栈
            stackCopy.push(in.poll());
            printAllOutStackSeq(in, stackCopy, outCopy);
        }
        return;
    }
}